from typing import List


class Solution:
    """
    方法：螺旋遍历矩阵
    Args:
        matrix: List[List[int]] - 二维整数矩阵
    Returns:
        List[int] - 按螺旋顺序排列的矩阵元素
    Time: O(m*n) - 需要遍历矩阵中的所有元素
    Space: O(1) - 只使用了常数个额外空间（不考虑输出结果的空间）
    """
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
         DIRS = (0, 1), (1, 0), (0, -1), (-1, 0) # 右下左上
         m, n = len(matrix), len(matrix[0])
         size = m * n
         ans = []
         i, j, di = 0, -1, 0 # 从 (0, -1) 开始
         while len(ans) < size:
            dx, dy = DIRS[di]
            for _ in range(n): # 走 n 步（注意 n 会减少）
                i += dx
                j += dy  # 先走一步
                ans.append(matrix[i][j]) # 再加入答案
            di = (di + 1) % 4 # 右转 90°
            n, m = m - 1, n  # 减少后面的循环次数（步数）
         return ans
    
    """
    方法：使用边界收缩法螺旋遍历矩阵
    
    Args:
        matrix: List[List[int]] - 二维整数矩阵
        
    Returns:
        List[int] - 按螺旋顺序排列的矩阵元素
        
    Time: O(m*n) - 需要遍历矩阵中的所有元素
    Space: O(1) - 只使用了常数个额外空间（不考虑输出结果的空间）
    """
    def spiralOrder1(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        res = []
        while top <= bottom and left <= right:
            # 从左到右遍历顶层
            for j in range(left, right + 1):
                res.append(matrix[top][j])
            top += 1
            # 从上到下遍历右列
            for i in range(top, bottom + 1):
                res.append(matrix[i][right])
            right -= 1
            if top <= bottom: # 防止单行重复
                # 从右到左遍历底层
                for j in range(right, left - 1, -1):
                    res.append(matrix[bottom][j])
                bottom -= 1
            if left <= right: # 防止单列重复
                # 从下到上遍历左列
                for i in range(bottom, top - 1, -1):
                    res.append(matrix[i][left])
                left += 1
        return res


